Kerberos/NTML No Longer Working

Ok, so apologies in advance - this is going to be a long one!

I came into work on Monday morning to get the "we can't get on to the server" from a couple of our Mac users. I didn't think much of it until I looked deeper into it. All the PC users were logged in fine (with Active Directory). None of the macs could get in. They would get the username and password dialog box and after they entered their correct credentials they were getting the old dialog box shake (as in, wrong username/password).

I tried a bunch of things to get them on and ended up resorting to logging on with the AD admin password just to get them working. It did, which meant they could work while I continued to investigate. From there I tried a bunch of things, probably not limited to -

Unbinding them from the domain

Trying them when not on the domain

Rebinding them

Different AD user accounts

Logging in with DOMAINNAME\username

Logging in with username@domainname

Connecting to the servers with DNS name and IP address

The results varied. Sometimes I thought I had a workaround only to find that on another machine it didn't work. Then back on the original machine it had stopped working as well. It has been a real head scratcher. Looking at the logs on the server I think that it is falling back to NTLM authentication and that is failing.

I'm really at a loss with this one. I'm assuming the issue is at the server level, but I'm not 100% as I can't find any identifying evidence. Any help or ideas much appreciated!! Details and server logs are below -

Environment Details

Domain: Active Directory

Domain Controller: Windows 2003 R2

Server: Windows 2008

Client: Mac OSX 10.8.5 (with some 10.9 and some 10.10 all patched)

Protocol: SMB (but have also tried CIFS)

FAILURE Log

Log Name: Security

Source: Microsoft-Windows-Security-Auditing

Date: 17/03/2015 12:29:47 PM

Event ID: 4625

Task Category: Logon

Level: Information

Keywords: Audit Failure

User: N/A

Computer: SERVERName.domain.name

Description:

An account failed to log on.

Subject:

Security ID: NULL SID

Account Name: -

Account Domain: -

Logon ID: 0x0

Logon Type: 3

Account For Which Logon Failed:

Security ID: NULL SID

Account Name: username

Account Domain: domain.name

Failure Information:

Failure Reason: An Error occured during Logon.

Status: 0xc000006d

Sub Status: 0x0

Process Information:

Caller Process ID: 0x0

Caller Process Name: -

Network Information:

Workstation Name: workstation

Source Network Address: xxx.xxx.xxx.xxx

Source Port: 49364

Detailed Authentication Information:

Logon Process: NtLmSsp

Authentication Package: NTLM

Transited Services: -

Package Name (NTLM only): -

Key Length: 0

----------------------------------------------------------------

SUCCESS Log

Log Name: Security

Source: Microsoft-Windows-Security-Auditing

Date: 17/03/2015 12:37:12 PM

Event ID: 4624

Task Category: Logon

Level: Information

Keywords: Audit Success

User: N/A

Computer: SERVERNAME.domain.name

Description:

An account was successfully logged on.

Subject:

Security ID: NULL SID

Account Name: -

Account Domain: -

Logon ID: 0x0

Logon Type: 3

New Logon:

Security ID: DOMAINNAME\username

Account Name: username

Account Domain: DOMAINNAME

Logon ID: 0x8ad5ffe

Logon GUID: {5637d44a-7e11-477c-daca-f1cea85d45r46}

Process Information:

Process ID: 0x0

Process Name: -

Network Information:

Workstation Name:

Source Network Address: xxx.xxx.xxx.xxx

Source Port: 56243

Detailed Authentication Information:

Logon Process: Kerberos

Authentication Package: Kerberos

Transited Services: -

Package Name (NTLM only): -

Key Length: 0